import time
import numpy as np
import matplotlib.pyplot as plt

def calcTime(func):
    '''
    函数修饰器, 用来计算求解所需糖果最小值的执行时间
    最终返回一个 list [temp, time_sum]
                    temp : 所需要糖果的最小数目
                    time_sum : 执行时间(单位ms)
    '''
    def warpper(ratings):
        time_start = time.perf_counter()
        temp = func(ratings)
        time_end = time.perf_counter()
        time_sum = time_end - time_start
        return [temp, time_sum *1000]
    return warpper

# 随机生成[0,10)的长度为n的分数数组ratings
def Ratings(n):
    ratings = np.random.randint(0, 10, size=n)
    return ratings

#求解所需糖果最小值
@calcTime
def candy(ratings):
    n=len(ratings)
    global left,right
    left = [1] * n
    right = left[:]
    count=0
    '''
        左遍历，保证左规则，即当前元素大于左边元素，就分配+1
    '''
    for i in range(1, n):
        if ratings[i] > ratings[i - 1]:
            left[i] = left[i - 1] + 1
    '''
        右遍历，保证右规则，即当前元素大于右边元素，就分配 + 1
    '''
    for i in range(n - 2, -1, -1):
        if ratings[i] > ratings[i + 1]:
            right[i] = right[i + 1] + 1
    '''
        满足左右规则最大值，则为最少分配糖果数
    '''
    for i in range(n):
        count += max(left[i], right[i])
    return count

#算法可视化
def Visual(x,y1,y2):
    bar_width = 0.3  # 条形宽度
    index_left = np.arange(len(x))    #左遍历条形图的横坐标
    index_right = index_left + bar_width  #右遍历条形图的横坐标

    # 使用两次 bar 函数画出两组条形图
    plt.bar(index_left, height=y1, width=bar_width, color='g', label='Left-Traversal')
    plt.bar(index_right, height=y2, width=bar_width, color='b', label='Right-Traversal')

    plt.legend()  # 显示图例
    plt.xticks(index_left + bar_width/2, x)  # 让横坐标轴刻度显示 x 里的值， index_left + bar_width/2 为横坐标轴刻度的位置
    plt.xlabel('ratings')  # 横坐标轴标题
    plt.ylabel('candynums')  # 纵坐标轴标题
    plt.title('The min candynums we need')  # 图形标题
    plt.show()


'''
测试：
if __name__ =='__main__':
    for i in range(5):
        list = Ratings(5)
        print('测试数据',i+1,'：',list,' ','运行结果：',candy(list))

    测试数据 1 ： [4 1 4 6 3]   运行结果： [9, 0.030099999999921856]
    测试数据 2 ： [1 0 5 6 6]   运行结果： [9, 0.025300000000005873]
    测试数据 3 ： [1 8 9 6 5]   运行结果： [9, 0.024200000000029753]
    测试数据 4 ： [8 6 6 6 1]   运行结果： [7, 0.023499999999954113]
    测试数据 5 ： [3 5 3 5 8]   运行结果： [9, 0.022999999999995246]


可视化测试：
if __name__ =='__main__':
    list = Ratings(5)
    print('Min candynums：', candy(list))
    print('ratings：',list)
    print('left ：',left)
    print('right：',right)
    Visual(list,left,right)

    Min candynums： [9, 0.010200000000071263]
    ratings： [3 2 9 4 2]
    left ： [1, 1, 2, 1, 1]
    right： [2, 1, 3, 2, 1]
'''